package leetcode;

import java.util.ArrayList;
import java.util.List;

public class LCode93 {
    private static List<String> list = new ArrayList<>();
    private static StringBuilder ipStr = new StringBuilder();
    public static List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return list;

    }
    public static void dfs(String s, int pointCount, int start) {
        if (start == s.length() && pointCount == 4) {
            list.add(ipStr.toString());
            return ;
        }
        if (start == s.length() || pointCount == 4) {
            return ;
        }
        // 剪枝【0,255】
        for (int i = start; i < s.length() && i - start < 3 && Integer.parseInt(s.substring(start, i + 1)) >= 0
                && Integer.parseInt(s.substring(start, i + 1)) <= 255; i++) {
            // 如果以0为开头，停止划分
            if (i - start > 0 && s.charAt(start) == '0') break;
            ipStr.append(s.substring(start, i + 1));
            // 如果点的数量小于3,就加点
            if (pointCount < 3) {
                ipStr.append(".");
            }
            pointCount++;
            dfs(s, pointCount, i + 1);
            pointCount--;
            ipStr.delete(start + pointCount, ipStr.length());
        }
    }

    /**
     * 输入：s = "25525511135"
     * 输出：["255.255.11.135","255.255.111.35"]
     *
     * 输入：s = "0000"
     * 输出：["0.0.0.0"]
     *
     * 输入：s = "101023"
     * 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
     * @param args
     */
    public static void main(String[] args) {
        List<String> strings = restoreIpAddresses("25525511135");
        for (String s:
             strings) {
            System.out.println(s);
        }

    }
}
